package com.zhaopin.theswordreferstooffer;

import java.util.LinkedHashMap;
import java.util.Map;

/**
 * @author yin.peide
 * @date 2021-06-25 17:09
 * 面试题35: 第一次只出现一次的字符
 * 解法1：最简单 拿第一个与后面依次比较，时间复杂度 O(n2)
 * 解法2：扫描两次，第一次把所有结果放到一个map中，有重复的累加value ,再第二次继续扫描串 找第一个value是1的就行
 */
public class Offer35 {

    public static void main(String[] args) {
        String s = "abaccdeff";
        System.out.println(getFirstOneChar(s));
        System.out.println(getFristOneChar2(s));
    }

    /**
     * 解法1
     *
     * @return
     */
    public static String getFristOneChar2(String str) {
        char[] charAttr = str.toCharArray();
        for (int i = 0; i < charAttr.length; i++) {
            for (int j = i+1; j < charAttr.length; j++) {
                if (charAttr[i] != charAttr[j]) {
                    if (j == charAttr.length - 1) {
                        return String.valueOf(charAttr[i]);
                    }
                    continue;
                } else {
                    //有相等的
                    break;
                }

            }

        }


        return null;
    }


    public static String getFirstOneChar(String str) {

        if (null == str) {
            return null;
        }

        Map<Character, Integer> map = new LinkedHashMap<>();
        for (char c : str.toCharArray()) {
            if (map.containsKey(c)) {
                int cValue = map.get(c);
                map.put(c, ++cValue);
            } else {
                map.put(c, 1);
            }
        }
        for (char c : str.toCharArray()) {
            if (map.get(c) == 1) {
                return String.valueOf(c);
            }
        }


        return null;
    }

}
